package com.ting.test.algorithms.递归和动态规划.从左往右的模型;

public class 背包问题解法2 {
    public static void main(String[] args) {
        int[] weight = new int[]{2, 3, 5, 7, 9, 0, 9};
        int[] value = new int[]{20, 23, 51, 7, 91, 10, 92};
        //由题意可知，我们 从0号货物开始计算货物的最大价值就是我们需要的答案
        int maxValue = beibao(weight, value, 0, 100);
        System.out.printf(maxValue + "");

    }

    private static int beibao(int[] weight, int[] value, int index, int bag) {
        int n = weight.length;
        int[][] dp = new int[n + 1][bag + 1];

        //根据递归可得  dp[n][*]=0 但 数组默认值就是0，可以不用处理 这样我们就得到了dp数组 最后一行的数据
        //这里 我们可以总结出来，在求解dp数组的时，需要先根据base case 或者其他条件推导出一些边界条件下的位置的值
        //然后再根据后续的递归调用的依赖关系，计算其他的值，比如当前题目 dp[index]就是依赖dp[index+1]的值，因此我们可以根据这些条件推导dp
        for (int current = n - 1; current >= 0; current--) {//由于我们已知的是dp[n]行的所有数据，而dp[index][*] 正好又依赖上一行dp[index+1]的值，因此循环从尾部往头部算
            for (int rest = 0; rest < bag; rest++) {
                int p1 = dp[current + 1][rest];
                int p2 = -1;
                int next = value[index + 1] + dp[index + 1][rest - weight[index]];
                if (next != -1) {
                    p2 = value[index] + next;
                }
                dp[index + 1][rest] = Math.max(p1, p2);
            }


        }
        return dp[index][bag];
    }

    /**
     * 这个递归函数，返回的是从第index个货物开始计算， 在背包空间为rest的情况下，能够获得的最大价值
     *
     * @param weight
     * @param value
     * @param index
     * @param rest
     * @return
     */
    private static int process(int[] weight, int[] value, int index, int rest) {
        //base case
        if (rest < 0) {
            return -1;//如果背包剩余空间小于0，则认为这种尝试情况是不存在的
            //注意，这里没有等于0，是因为有可能有些物品的重量是0，但是他是有价值的
        }
        if (index == weight.length) {
            //表示货物都已经放完了
            return 0;

        }

        //如果背包还有空间,则需要考虑两种情况/
        //1. 当前物品不放入背包 ，则这种情况的最大价值是不包含当前物品的
        int p1 = process(weight, value, index + 1, rest);
        int p2 = -1;

        //先判断如果当前货物放入背包，后续是否还能够放货物
        int next = process(weight, value, index + 1, rest - weight[index]);
        //注意 如果next返回-1 则表示，当前货物放进去之后，背包的rest<0了，也就是说当前货物实际上是放不进去的
        if (next != -1) {
            //如果当前物品放入背包，则最大价值是，当前物品的价值+后续的所有物品的最大价值
            p2 = value[index] + next;
        }
        return Math.max(p2, p1);
    }

}
